本文译自论文：https://arxiv.org/pdf/1402.6407.pdf，主要讲述了Roaring bitmap相较其他压缩方案表现出来的优势 ，包括存取速度，内存占用，按位取交集和并集的效率等，并附有实际的测试比对。

通过本文你能学到什么？

1.什么是bitmap？为什么使用bitmap？Roaring bitmap与其他bitmap编码技术相比有哪些优势？2.Roaring bitmap将32位无符号整数按照高16位分容器，即最多可能有216=65536个容器(container)，存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。高16位又称为共享有效位，它用于索引应该到哪个容器中查找对应的数值，属于roaring bitmap的一级索引。3.Roaring bitmaps以紧凑高效的两级索引数据结构存储32位整数。高密度块使用位图存储;稀疏块使用16位整数的压缩数组。当一个块包含不超过4096个整数时，我们使用一个排好序的16位整数数组。当有超过4096个整数时，我们使用2^16 位的位图。为什么按4096作为阀值呢？仅仅是因为当数据块中的整数数量超过这个值之后，bitmap将比数组的内存使用率更高。

4.为了检查32位整数x是否存在，我们首先使用二进制搜索查找对应于x/2^16^ 的容器。如果找到位图容器，则访问第(x对2^16取模)位。如果找到数组容器，则再次使用二分搜索。同样地，我们插入和删除一个整数x。我们首先寻找相应的容器。当找到的容器是位图时，我们设置相应位的值并相应地更新基数。如果找到数组容器，则使用二分查找，然后执行线性时间插入或删除操作。在删除整数时，如果位图容器的基数达到4096，则该位图容器可能成为数组容器。在添加整数时，当数组容器的基数超过4096时，它可能成为位图容器。当发生这种情况时，将使用更新后的数据创建一个新的容器，同时丢弃旧的容器。将数组容器转换为位图容器的方法是创建一个用零初始化的新位图容器，并设置相应的位。要将位图容器转换为数组容器，我们使用优化算法提取集合位的位置。计算两个数组容器的交集时也是采取二分查找（要求数组中数值有序）。5.两个Roaring bitmap之间可以通过AND和OR位操作快速进行交集和并集计算。6.bitmap比较适用于数据分布比较稠密的存储场景中，对于原始的Bitmap来说，这就需要2 ^ 32长度的bit数组 通过计算可以发现(2 ^ 32 / 8 bytes = 512MB), 一个普通的Bitmap需要耗费512MB的存储空间。因为redis的bitmap数据结构是用string实现的，其大小为512M，所以在redis中就存在这个问题。Roaring bitmap会对数据块的基数进行统计，当基数小于4096时会用一个数组来存储，当基数大于4096时对应的则是一个BitmapContainer。BitmapContainer存储空间恒定为8k，最大基数可达8 * 1024 * 8 = 65536个。每个long有64位，因此需要1024个long来提供65536个bit。每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。7. 经过测试对比后发现Roaringbitmap与其他bitmap压缩算法相比往往表现得更好。8. 原生的 RoaringBitmap 只存储整形数据，32 位的 RoaringBitmap 最大的数据存储量是 2147483647。像订单、流量这样的数据量可以采用 64 位的 RoaringBitmap，但在性能上 32 位的效率在同等条件下要优于 64 位。

Bitmap索引经常被用在数据库和搜索引擎中。通过利用位级并级度的优势，它能够显著地加速查询。但是，它也有一个缺点，那就是会耗费更多的内存，因此我们可能更偏向于压缩的BitMap索引。在Oracle的领导下，位图通常使用运行长度编码(RLE)进行压缩。在先前工作的基础上，我们引入了Roaring Bitmap格式，它使用压缩数组而不是RLE。我们将其与两种基于RLE的高性能的bitmap编码技术进行了比较：WAH(Word Aligned Hybrid compression scheme) 和Concise((Compressed ‘n’ Composable Integer Set)。在创造的和真实的数据上，我们发现Roaring bitmaps经常比其他压缩方案表现的更好（２倍以上），而且比其他压缩方案更快（交集比较速度达到其他方案的900倍）。我们的结果向认为基于RLE的压缩方案最好的观点发起了挑战。

关键字： 性能；度量；索引压缩；bitmap索引

我们可以把一个bitmap或者bitset看作是一个用高效紧凑的整数集S表示的二进制数组。给一个bitmap设置为n位，如果在[0,n-1]范围内的第i个整数存在于集合中，则第i位设置为1。例如，集合{3,4,7}和集合{4,5,7}可以以二进制存储为10011000和10110000。我们可以在位图(例如，10111000和10010000)上使用按位操作(or, AND)计算两个对应列表之间的并集或交集。bitmap是Java平台(java.util.BitSet)的一部分。

当S的基数相对于宇宙大小相对较大时，n(例如，在64位处理器上|S| > n/64 )，位图通常优于其他类似的数据结构，如数组、哈希集或树。然而，在中等密度的位图(n/10000 i。图2e显示，Roaring所需的时间少于WAH和Concise。此外，与Roaring位图不同，WAH和Concise不支持以随机顺序有效地插入值。最后，我们测量了从一个随机选择元素中删除一个随机选择的元素所需的时间整数集（图2f）。我们观察到Roaring位图比其他两种压缩格式具有更好的结果。

表I II显示了五个真实数据集的结果，这些数据集使用了早期对压缩位图索引[15]的研究。只有两个例外：

•我们只将1985年9月的数据用于天气数据集(其他人在[16]之前使用过的一种方法)，否则它对于我们的测试环境来说太大了。•我们省略了CENSUS2000数据集，因为它只包含在一个大宇宙(n = 37 019 068)中平均基数为30的位图。对于位图来说，这是一个不适合的场景。由于结构开销，Roaring bitmap使用的内存和Concise位图一样多。然而，当计算交集时，Roaring位图要快4倍。

数据集是按原样获取的:在建立索引之前，我们没有对它们排序。

对于每个数据集，都建立了位图索引。然后，我们从索引中选择200位图，使用类似于分层抽样的方法来控制属性基数的大范围。我们首先抽样200个属性，并进行替换。对于每个采样的属性，我们随机选择其中一个位图。使用200位图作为100对输入的100对AND和OR操作;表IIb和IIc显示了当Roaring被BitSet, WAH或Concise取代时，时间因子增加。(值低于1.0表示Roaring速度较慢。)表IIa显示了当Roaring被其他方法之一取代时存储因子的增加。

一般来说，Roaring bitmap总是比WAH和Concise更快。在两个数据集(CENSUS1881和WIKILEAKS)上，Roaring bitmap比BitSet快，同时使用更少的内存(少40个)。在另外两个数据集上，BitSet的速度是Roaring bitmap的两倍多，但它也使用了三倍的内存。当比较BitSet和Roaring bitmap的速度时，可以考虑Roaring bitmap预先计算块级别的基数。因此，如果我们需要聚合位图的基数，Roaring bitmap就有优势。在WIKILEAKS的数据集上，Concise和WAH提供了比Roaring更好的压缩(大约30%)。这是由于存在一个长时间的运行(11···1填充词)，Roaring bitmap不会压缩。

CENSUS1881数据集的结果是惊人的:Roaring比其他方法快了900倍。这是由于位图的基数有很大的差异。当稀疏的位图与稠密的位图取交集时，Roaring是特别有效的。

本文介绍了一种新的位图压缩方案——Roaring。它将位图集项存储为32位整数，存储在一个空间效率高的两级索引中。与两种有竞争力的位图压缩方案相比，WAH和Concise，Roaring通常使用更少的内存和更快。当数据是有序的，位图需要存储长期连续的值(例如，在WIKILEAKS数据集)，替代方案，如Concise或WAH可能提供更好的压缩比。然而，即使在这些情况下，Roaring也可能更快。在未来的工作中，我们将考虑进一步提高性能和压缩比。我们可以添加新类型的容器。特别是，我们可以使用快速封装技术来优化数组容器[17]的存储使用。我们可以在算法中使用SIMD指令[18,19,20]。我们还应该回顾除交集和并集之外的其他操作，比如阈值查询[21]。我们计划进一步研究在信息检索方面的应用。我们有理由感到乐观:Apache Lucene(从5.0版开始)已经采用了一种Roaring格式[22]来压缩文档标识符。

32位的RoaringBitmap获取高低16位的实现：

•Colantonio A, Di Pietro R. Concise: Compressed ’n’ Composable Integer Set. Information Processing Letters 2010; 110(16):644–650, doi:10.1016/j.ipl.2010.05.018.•Antoshenkov G. Byte-aligned bitmap compression. DCC’95, IEEE Computer Society: Washington, DC, USA, 1995; 476.•Wu K, Stockinger K, Shoshani A. Breaking the curse of cardinality on bitmap indexes. SSDBM’08, Springer: Berlin, Heidelberg, 2008; 348–365.•Lemire D, Kaser O, Aouiche K. Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering 2010; 69(1):3–28, doi:10.1016/j.datak.2009.08.006.•Fusco F, Stoecklin MP, Vlachos M. NET-FLi: On-the-fly compression, archiving and indexing of streaming network traffic. Proceedings of the VLDB Endowment 2010; 3(2):1382–1393, doi:10.14778/1920841.1921011.•Corrales F, Chiu D, Sawin J. Variable length compression for bitmap indices. DEXA’11, Springer-Verlag: Berlin, Heidelberg, 2011; 381–395.•Guzun G, Canahuate G, Chiu D, Sawin J. A tunable compression framework for bitmap indices. ICDE’14, IEEE, 2014; 484–495.•Culpepper JS, Moffat A. Efficient set intersection for inverted indexing. ACM Transactions on Information Systems Dec 2010; 29(1):1:1–1:25, doi:10.1145/1877766.1877767.•Kaser O, Lemire D. Attribute value reordering for efficient hybrid OLAP. Information Sciences 2006; 176(16):2304–2336.•O’Neil E, O’Neil P, Wu K. Bitmap index design choices and their performance implications. IDEAS’07, IEEE, 2007; 72–84.•Rinfret D, O’Neil P, O’Neil E. Bit-sliced index arithmetic. Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, ACM: New York, NY, USA, 2001; 47–57, doi:10.1145/375663. 375669.•Warren HS Jr. Hacker’s Delight. 2nd ed. edn., Addison-Wesley: Boston, 2013.•Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I. Spark: Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, USENIX Association: Berkeley, CA, USA, 2010; 10–10.•Yang F, Tschetter E, Léauté X, Ray N, Merlino G, Ganguli D. Druid: A real-time analytical data store. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD ’14, ACM: New York, NY, USA, 2014; 157–168, doi:10.1145/2588555.2595631.•Lemire D, Kaser O, Gutarra E. Reordering rows for better compression: Beyond the lexicographical order. ACM Transactions on Database Systems 2012; 37(3), doi:10.1145/2338626.2338633. Article 20. BETTER BITMAP PERFORMANCE WITH ROARING BITMAPS 11•Beyer K, Ramakrishnan R. Bottom-up computation of sparse and iceberg CUBEs. SIGMOD Record 1999; 28(2):359–370, doi:10.1145/304181.304214.•Lemire D, Boytsov L. Decoding billions of integers per second through vectorization. Software: Practice and Experience 2015; 45(1), doi:10.1002/spe.2203.•Polychroniou O, Ross KA. Vectorized bloom filters for advanced simd processors. Proceedings of the Tenth International Workshop on Data Management on New Hardware, DaMoN ’14, ACM: New York, NY, USA, 2014; 1–6, doi:10.1145/2619228.2619234.•Lemire D, Boytsov L, Kurz N. SIMD compression and the intersection of sorted integers. http://arxiv.org/ abs/1401.6399 [last checked March 2015] 2014.•Inoue H, Ohara M, Taura K. Faster set intersection with SIMD instructions by reducing branch mispredictions. Proceedings of the VLDB Endowment 2014; 8(3).•Kaser O, Lemire D. Compressed bitmap indexes: beyond unions and intersections. Software: Practice and Experience 2014; doi:10.1002/spe.2289. In Press.•Grand A. LUCENE-5983: RoaringDocIdSet. https://issues.apache.org/jira/browse/ LUCENE-5983 [last checked March 2015] 2014

[1] WAH: http://www.openproceedings.org/2010/conf/edbt/DeliegeP10.pdf [2] Concise: https://arxiv.org/pdf/1402.6407.pdf